1. Field of the Invention
The present invention relates to a control device and a method, which are related to a branch prediction of a microprocessor.
2. Description of Related Art
A microprocessor which performs a pipeline process simultaneously executes a number of instructions like an assembly line operation. However, when a branch instruction occurs during the execution of instructions, the pipeline stalls because the processor does not know whether to take the instruction or not until the branch instruction is completed.
If the processor waits for the completion of the process of the branch instruction, then the process misses the chances of reading and issuing a number of instructions. A branch prediction predicts whether to perform a branch operation according to a branch instruction, fetches the next instruction, and then loads the instruction into the pipeline. If the prediction is correct, then the instruction can be continued without stalling the pipeline. If the prediction is incorrect, an instruction fetch is performed using an address in a correct branch direction to resume the execution process. A failure of this branch prediction is referred to as a branch prediction miss. When a branch prediction miss occurs, the pipeline stalls. Then, an instruction in a correct branch direction is fetched and loaded into the pipeline to be executed. The period of time until the instruction is executed is referred to as a branch prediction miss penalty. The microprocessor with many pipeline stages where instructions are fetched and executed increases the branch prediction miss penalty when the branch prediction is incorrect. Consequently, severe performance degradation is caused. For that reason, prediction accuracy is critically important in the branch prediction.
Further, there are microprocessors which perform a speculative execution, to increase the effect of the branch prediction. Here, the speculative execution means that an instruction of a branch prediction target is executed in advance according to the branch prediction. In other words, this is a function by which the instruction subsequent to the branch prediction is executed before it is found if the branch prediction is correct or incorrect.
A technique related to a conventional branch prediction is disclosed in Patent Document 1. Patent Document 1 discloses an instruction fetch control device which performs, at a high speed, a sequence of instructions such as a subroutine call/return instruction in a microprocessor. FIG. 10 is a block diagram illustrating the instruction fetch control device according to Patent Document 1. The device disclosed in Patent Document 1 has a structure including a return address stack 301 and a branch history 302 for the branch prediction of a return instruction.
The return address stack (hereinafter, referred to as an RAS) 301 is a register which stacks a return address of a subroutine. The RAS 301 performs a push process on a return address at the time of completion of a call instruction. That is, an execution position is moved to a designated address by the call instruction, and thereafter, a return address or the address information of the next instruction is stored in the RAS 301 in order to operate a stack pointer. Further, the RAS 301 performs a pop process on the return address at the time of the completion of the return instruction. That is, the execution position is moved to the return address taken out from the RAS 301 by the return instruction, or to an address of the next instruction, in order to operate the stack pointer.
The branch history 302 is a table in which the history information of past branch predictions is stored. A stack pointer value is changed by the push process or the pop process of the RAS 301. A branch prediction address is read from one of the RAS 301 and the branch history 302 according to the value.
In an instruction fetch control unit 300 shown in FIG. 10, once an instruction is fetched, instruction codes are read from an instruction cache 305 and the branch history 302 according to an address outputted from an instruction address generator 304. When a selection controller 306 recognizes an instruction code as a return instruction, the selection controller 306 refers to a stack pointer. The selection controller 306 then outputs a selection signal for selecting from which the RAS 301 or the branch history 302 a prediction branch target address is to be read. Thereafter, the following instruction fetch is performed using the selected prediction branch target address. As to the stack pointer, when a completed instruction is a call instruction, a push process is performed on the stack pointer, and when the completed instruction is a return instruction, a pop process is performed on the stack pointer. As described above, the branch prediction of the return instruction is performed by including the RAS 301 and the branch history 302 in Patent Document 1. Note that, when a branch prediction miss occurs and a reinstruction fetch occurs, the stack pointer is retuned to a minimum value, and the process is restarted from the beginning.
However, in Patent Document 1, the pointer control of the RAS 301 is performed at the completion of the subroutine call/return instruction. Thus, in the case where the execution of the subsequent instruction fetch and the return instruction in the prediction branch target address are close in time, the branch prediction miss occurs frequently when only the RAS 301 performs the branch prediction. For example, when a return instruction is issued before the completion of a call instruction due to the advance reading of a prediction branch target address of the call instruction, or the like (at the time of the speculative fetching of an instruction), the branch prediction miss occur frequently because the return address is not stored in the RAS 301. Therefore, in the conventional technique, in a case where a return instruction which cannot be handled with a return address, the accuracy of the branch prediction is improved by using the branch history 302 together with the RAS 301.
To solve the above-described problems, Patent Document 2 is disclosed. Patent Document 2 has an aspect including a first RAS for storing a return address until a call instruction is executed, and a second RAS for storing the return address after the call instruction is executed. A return target can be predicted by using the first RAS until the call instruction is executed, and by using the second RAS after the call instruction is executed. At this time, it is determined which address an output selection circuit selects in accordance with information detected by the branch history.    [Patent Document 1] Japanese Patent Application Publication No. 2000-172507    [Patent Document 2] Japanese Patent Application Publication No. 2006-40173
However, the inventors found out that the conventional techniques have the following problems. The conventional techniques predict the presence of a subroutine call/return instruction using the branch history. For the branch history, when the capacity is large, the effect of a branch prediction is increased; however, when the circuit size is increased, it becomes very costly. Therefore, to perform a branch prediction with high accuracy, it is necessary to use a costly branch history. In addition, there is a problem that the branch history needs a period of time to learn a past history.